The present invention relates to a modular multiplication processing apparatus used in the field of security. More particularly, it relates to an implementation technique to a cryptosystem device mounted on a server, a smart card, or the like.
<Fundamentals of RSA Cryptosystem>
RSA cryptosystem that is the first public key cryptosystem in the world that was invented in 1978 has a nature that a key for encryption and a key for decryption are different and the key for encryption (public key) can be opened. In the RSA cryptosystem, modular exponentiation C=Lemod K is performed in order to transform plaintext L to ciphertext C. Here, “e” and “K” are the public keys for encryption. In the RSA cryptosystem, decryption can be performed by only changing exponent from “e” to a value of a private key for decryption (private key) d. At least 1,024 bits are frequently used for modulus K that is the public key and the private key d in view of security.
<Demand for Fast Modular Multiplication>
Time-consuming modular exponentiation is required in public key cryptosystem such as the RSA cryptosystem. Therefore, in an IC card (smart card) on which a CPU with high performance cannot be mounted or a server apparatus to which administrations are centralized, an execution time is often shortened by using a coprocessor implemented with modular multiplication as hardware. Especially, Montgomery multiplication described in A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography pp. 599-pp. 603 (1997) (herein, Document1) is known as a processing method of fast modular multiplication implemented on many hardwares. As a speed-up method of modular multiplication, a method applied with Montgomery multiplication (hereinafter, called “bipartite modular multiplication”) is described in M. Kaihara, N. Takagi: “Bipartite Modular Multiplication” CHES2005, vol. 3659 of Lecture Notes in Computer Science, Springer-Verlag, pp. 201-210 (2005) (hereinafter, Document4).
<Decryption of RSA Cryptosystem>
Means for applying a method for dividing arithmetic operation to perform modular multiplication exceeding the number of bits in a coprocessor at high speed is known for processing RSA cryptosystem at high speed. In most of the methods, since information of a private key is required for the division of arithmetic operation, such methods can be utilized in decryption (or signature generation) processing of the RSA cryptosystem.
<Encryption of RSA Cryptosystem>
In encryption of RSA cryptosystem (or signature verification) processing, a research for performing modular multiplication exceeding the number of bits in a coprocessor at high speed like the decryption processing is described in W. Fischer, J. -P. Seifert: “Increasing the bit-length of crypto-coprocessors” CHES2002, vol. 2523 of Lecture Notes in Computer Science, Springer-Verlag, pp. 71-81 (2003) (hereinafter, called Document2) and Benoit Chevallier-Mames, Marc Joye, and Pascal Paillier: “Faster Double-Size Modular Multiplication From Euclidean Multipliers” CHES2003, vol. 2779 of Lecture Notes in Computer Science, Springer-Verlag, pp. 214-227 (2003) (hereinafter, called Document3). Since it is possible to perform modular multiplication of data with a bit length of at most twice (2n) the bit length of a coprocessor whose bit length is a positive integer n by using the coprocessor, encryption processing of RSA cryptosystem having a key length of at most 2n-bit can be performed using a coprocessor with n-bit.